'''
https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-interview-150
'''
from functools import cache
from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)

        @cache
        def f(rest):
            if rest == 0:
                return 0
            res = float('inf')
            for coin in coins:
                if coin <= rest:
                    res = min(res, f(rest - coin) + 1)
            return res
        res = f(amount)
        return -1 if res == float('inf') else res

    def coinChange2(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for rest in range(1, amount + 1):
            res = float('inf')
            for coin in coins:
                if coin <= rest:
                    res = min(res, dp[rest - coin] + 1)
            dp[rest] = res
        return -1 if dp[-1] == float('inf') else dp[-1]
